//你总共需要上
// numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中
// prerequisites[i] = [ai, bi] 表示如果你想选
// bi 课程，你 必须 先选
// ai 课程。 
//
// 
// 有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。 
// 
//
// 先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。 
//
// 你也得到一个数组
// queries ，其中
// queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程
// uj 是否是课程
// vj 的先决条件。 
//
// 返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
//输出：[false,true]
//解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。
// 
//
// 示例 2： 
//
// 
//输入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
//输出：[false,false]
//解释：没有先修课程对，所以每门课程之间是独立的。
// 
//
// 示例 3： 
//
// 
//
// 
//输入：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]
//]
//输出：[true,true]
// 
//
// 
//
// 提示： 
//
// 
// 
//
// 
// 2 <= numCourses <= 100 
// 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2) 
// prerequisites[i].length == 2 
// 0 <= ai, bi <= n - 1 
// ai != bi 
// 每一对
// [ai, bi] 都 不同 
// 先修课程图中没有环。 
// 1 <= queries.length <= 10⁴ 
// 0 <= ui, vi <= n - 1 
// ui != vi 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 163 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2023-09-12 16:00:02
 * @description 1462.课程表 IV
 */
public class CourseScheduleIv{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CourseScheduleIv().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //保存边
	List<List<Integer>> edge;
	//是否访问
	boolean [] vis;
	//是不是先决条件
	boolean[][] isPre;
    public List<Boolean> checkIfPrerequisite1(int numCourses, int[][] prerequisites, int[][] queries) {
			List<Boolean> res=new ArrayList<>();
			isPre=new boolean [numCourses][numCourses];
			edge=new ArrayList<>();
			vis=new boolean[numCourses];
			//至少有这么多条边
		for (int i = 0; i < numCourses; i++) {
			edge.add(new ArrayList<>());
		}
		//把每个先决条件课程的后置课程加入边
		for (int[] prerequisite : prerequisites) {
			edge.get(prerequisite[0]).add(prerequisite[1]);
		}
		//遍历每个点
		for (int i = 0; i < numCourses; i++) {
			dfs(edge,isPre,vis,i);
		}
		// o（1）返回结果
		for (int[] query : queries) {
			res.add(isPre[query[0]][query[1]]);
		}
		return res;
    }
	private void dfs(List<List<Integer>> edge,boolean [][] isPre,boolean[] vis,int i){
		//如果已经访问了就返回
		if(vis[i]){
			return;
		}
		//标记
		vis[i]=true;
		for (int ne : edge.get(i)) {
			dfs(edge,isPre,vis,ne);
			//当前节点是其后继课程的先觉条件
			isPre[i][ne]=true;
			//当前课程是他的后继课程的后继课程的先决条件
			for (int j = 0; j < isPre.length; j++) {
				isPre[i][j]=isPre[i][j]|isPre[ne][j];
			}
		}
	}
	/*bfs
	* 从入度开始，把入度为0的点加入*/
	public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries){
		List<Boolean> res=new ArrayList<>();
		isPre=new boolean [numCourses][numCourses];
		edge=new ArrayList<>();
		vis=new boolean[numCourses];
		//入度
		int[] indgree = new int[numCourses];
		for (int i = 0; i < numCourses; i++) {
			edge.add(new ArrayList<>());
		}
		for (int[] prerequisite : prerequisites) {
			edge.get(prerequisite[0]).add(prerequisite[1] );
			++indgree[prerequisite[1]];
		}
		Queue<Integer> queue=new ArrayDeque<>();
		for (int i = 0; i < numCourses; i++) {
			if(indgree[i]==0){
				queue.offer(i);
			}
		}
		while (!queue.isEmpty()){
			int curr= queue.poll();
			for (int ne : edge.get(curr)) {
				//当前节点是他的后继节点的先决条件
				isPre[curr][ne]=true;
				for (int i = 0; i < numCourses; i++) {
					//其他节点是当前节点的先决条件则是当前课程后继课程的先决条件
					isPre[i][ne]=isPre[i][ne]|isPre[i][curr];
				}
				--indgree[ne];
				//入度为0又加入
				if(indgree[ne]==0){
					queue.offer(ne);
				}
			}
		}
		for (int[] query : queries) {
			res.add(isPre[query[0]][query[1]]);
		}
		return res;
	}



}
//leetcode submit region end(Prohibit modification and deletion)

}
